The topology of a distributed processing network, such as an Internet Protocol network, is information with many potential uses in troubleshooting, administration, planning, and other tasks. “Topology” refers generally to the patterns of connection between the various machines in a network, and “topology information” refers to the body of information associated therewith. Complete and accurate network topology information can predict the path of an individual packet through the network and hence identify the set of network devices, such as routers and their associated interfaces, involved. Incorrect or inaccurate information can lead to poor planning and/or administrative decisions, an inability to accurately measure network performance, and/or consumption of excessive resources in troubleshooting problems, particularly in IP telephony where jitter and packet round trip time can be crucial considerations.
Current solutions to the problem of topology discovery can be separated into two broad categories, namely Simple Network Management Protocol or SNMP-based and traceroute-based. The majority of current commercial products, such as Avaya ExpertNet™ and Hewlett Packard Open View™, use an SNMP-discovery mechanism to construct topology information. In this approach, topology information is obtained from the Management Information Base or MIB of one or more routers in the network segment or subnetwork of interest. The topology information in the MIB can, however, be incomplete and/or inaccurate. Neither of the two standardized routing tables available through SNMP, namely IpRouteTable (RFC1213) and IpCidrRouteTable (RFC 2096), are capable of containing the multiple routes, or redundant links, having the same metric or cost to a selected destination. Traceroute-based techniques are available on a number of major operating systems, such as Windows™, Unix, and Linux. Traceroute sends a series of Internet Control Message Protocol or ICMP packets, each with an increasing Time-To-Live or TTL, to a particular destination device. It then uses error messages that are returned from each router on-route when the TTL expires to construct the path to that destination. Although the traceroute technique can have an advantage over SNMP-based techniques, namely that traceroute takes into account the actual routing decisions that are made on packets traveling across the network, traceroute can return an incorrect path that is made up of some combination of two or more physically separate paths, particularly when load balancing is in effect.
Both techniques are generally unable to detect the existence of load balancing, let alone the type of load balancing, in effect along a route. With reference to FIG. 1, there are two redundant links or paths depicted, namely the first path from router 100 to router 104 to router 112 and the second path from router 100 to router 108 to router 112. The redundant links permit traffic to be distributed across the multiple routes to use network resources more efficiently. In per-packet load balancing, each outgoing packet is queued to a router interface in a round-robin fashion. In other words, a first packet is sent along the first path, a second (next) packet along the second path, a third (next) packet along the first path, and so on. This type of load balancing can cause voice telephony packets to arrive out of sequence at the destination, which appears to the destination as jitter. In per-destination load balancing, each router interface caches the destination address of each packet such that the next packet addressed to the same destination will be sent down the same interface. In per-source/destination load balancing, better usage of per-destination of load balancing is obtained by caching both the destination and the source address at each router interface. This ensures that the next packet with the same to/from address pair is sent down the same interface. Load balancing can not only be detrimental to IP telephony but also cause difficulties in measuring link characteristics as it can become difficult determining exactly to which link the measured characteristics correspond.